/*
 * This file is part of Cadmium.
 * Copyright (C) 2007-2010 Xavier Clerc.
 *
 * Cadmium is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Cadmium is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package fr.x9c.cadmium.primitives.stdlib;

import fr.x9c.cadmium.kernel.Block;
import fr.x9c.cadmium.kernel.CodeRunner;
import fr.x9c.cadmium.kernel.Custom;
import fr.x9c.cadmium.kernel.Primitive;
import fr.x9c.cadmium.kernel.PrimitiveProvider;
import fr.x9c.cadmium.kernel.Value;
import fr.x9c.cadmium.util.Misc;

/**
 * Implements all primitives from 'hash.c'.
 *
 * @author <a href="mailto:cadmium@x9c.fr">Xavier Clerc</a>
 * @version 1.0
 * @since 1.0
 */
@PrimitiveProvider
public final class Hash {

    /**
     * No instance of this class.
     */
    private Hash() {
    } // end empty constructor

    /**
     * Computes the hash of a given value.
     * @param ctxt context
     * @param count maximum number of meaningful nodes to explore
     * @param limit maximum number of nodes to explore
     * @param obj value to hash
     * @return hash of <tt>obj</tt>
     */
    @Primitive
    public static Value caml_hash_univ_param(final CodeRunner ctxt,
                                             final Value count,
                                             final Value limit,
                                             final Value obj) {
        final HashParams hp = new HashParams(limit.asLong(), count.asLong());
        hashVal(obj, hp, true);
        return Value.createFromLong(hp.get());
    } // end method 'caml_hash_univ_param(CodeRunner, Value, Value, Value)'

    /**
     * Computes the hash value of a string representing a variant or
     * method name.
     * @param s variant or method name
     * @return hash value of <tt>s</tt>
     */
    public static Value hashVariant(final String s) {
        int res = 0;
        final int len = s.length();
        for (int i = 0; i < len; i++) {
            res = (223 * (res >> 1) + Misc.signedToUnsignedByte(Misc.convertCharToByte(s.charAt(i)))) << 1;
        } // end for
        return Value.createFromLong(res >> 1);
    } // end method 'hashVariant(String)'

    /**
     * Hashes a value.
     * @param obj value to hash
     * @param hash hash struture to update and to get parameters from
     * @param count whether to count value with respect to hash limit
     */
    private static void hashVal(final Value obj,
                                final HashParams hash,
                                final boolean count) {
        if (count) {
            hash.decrementLimit();
            if (hash.stopHashing()) {
                return;
            } // end if
        } // end if

        if (obj.isLong()) {
            hash.decrementCount();
            hash.combine(obj.asLong());
            return;
        } // end if

        final Block block = obj.asBlock();
        final int tag = block.getTag();
        switch (tag) {
        case Block.STRING_TAG:
            hash.decrementCount();
            final byte[] chars = block.getBytes();
            final int lenChars = chars.length;
            for (int i = 0; i < lenChars; i++) {
                hash.combineSmall(Misc.signedToUnsignedByte(chars[i]));
            } // end for
            break;
        case Block.DOUBLE_TAG:
            hash.decrementCount();
            hashDouble(block.asDouble(), hash);
            break;
        case Block.DOUBLE_ARRAY_TAG:
            hash.decrementCount();
            final int lenDbl = block.sizeDoubles();
            for (int i = 0; i < lenDbl; i++) {
                hashDouble(block.getDouble(i), hash);
            } // end for
            break;
        case Block.ABSTRACT_TAG:
            break;
        case Block.INFIX_TAG:
            hashVal(Value.createFromBlock(block.getParent()),
                    hash,
                    true);
            break;
        case Block.FORWARD_TAG:
            hashVal(block.get(0), hash, false);
            return;
        case Block.OBJECT_TAG:
            hash.decrementCount();
            hash.combine(block.get(1).asLong());
            break;
        case Block.CUSTOM_TAG:
            final Custom.Operations ops = block.getCustomOperations();
            if (ops.isHashable()) {
                hash.decrementCount();
                hash.combine(ops.hash(obj));
            } // end if
            break;
        default:
            hash.decrementCount();
            hash.combineSmall(tag);
            final int lenBl = block.sizeValues();
            for (int i = lenBl - 1; i >= 0; i--) {
                hashVal(block.get(i), hash, true);
            } // end for
            break;
        } // end switch
    } // end method 'hashVal(Value, HashParams, boolean)'

    /**
     * Hashes a double value.
     * @param d value to hash
     * @param hash hash struture to update
     */
    private static void hashDouble(final double d, final HashParams hash) {
        final long bits = Double.doubleToRawLongBits(d);
        for (int i = 0; i < 8; i++) {
            hash.combineSmall((int) ((bits >> (i * 8)) & 0xFF));
        } // end for
    } // end method 'hashDouble(double, HashParams)'

    /**
     * This class represents the current state of a hash value. <br/>
     * Used to make hashing thread-safe (<i>i. e.</i> does not rely upon
     * runtime lock).
     */
    private static final class HashParams {

        /** Used to combine large values. */
        private static final int ALPHA = 65599;

        /** Used to combine small values. */
        private static final int BETA = 19;

        /** Current hash value. */
        private long accu;

        /** Maximum number of sub-values to hash (limit). */
        private int limit;

        /** Maximum number of sub-values to hash (count). */
        private int count;

        /**
         * Constructs a hash structure.
         * @param lim maximum number of sub-values to hash (limit)
         * @param cnt maximum number of sub-values to hash (count)
         */
        private HashParams(final int lim, final int cnt) {
            this.accu = 0L;
            this.limit = lim;
            this.count = cnt;
        } // end constructor(int, int)

        /**
         * Tests whether hashing should stop.
         * @return <tt>true</tt> if hashing should stop, <tt>false</tt> othewise
         */
        private boolean stopHashing() {
            return (this.count < 0) || (this.limit < 0);
        } // end method 'stopHashing()'

        /**
         * Decrements the number of sub-values to hash (count).
         */
        private void decrementCount() {
            this.count--;
        } // end method 'decrementCount()'

        /**
         * Decrements the number of sub-values to hash (limit).
         */
        private void decrementLimit() {
            this.limit--;
        } // end method 'decrementLimit()'

        /**
         * Combines the current hash value with another (small) value.
         * @param x value to combine hash value with
         */
        private void combineSmall(final int x) {
            this.accu = this.accu * Hash.HashParams.BETA + x;
        } // end method 'combineSmall(int)'

        /**
         * Combines the current hash value with another (large) value.
         * @param x value to combine hash value with
         */
        private void combine(final int x) {
            this.accu = this.accu * Hash.HashParams.ALPHA + x;
        } // end method 'combine(int)'

        /**
         * Returns the current hash value.
         * @return the current hash value
         */
        private int get() {
            return (int) (this.accu & 0x3FFFFFFF);
        } // end method 'get()'

    } // end inner-class 'HashParams'

} // end class 'Hash'
